package com.test.daily.leetcode.y2022.m06.day0614.v02;

import java.util.LinkedList;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/14 上午 08:49
 * @version: 1.0
 */
public class Solution {
    public static boolean[] bestStart(int[] g, int[] c) {
        int N = g.length;
        int M = N >> 1;
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = g[i] - c[i];
            arr[i + N] = g[i] - c[i];
        }
        for (int i = 1; i < M; i++) {
            arr[i] = arr[i] + arr[i - 1];
        }
        LinkedList<Integer> minQ = new LinkedList<Integer>();
        for (int i = 1; i < N; i++) {
            if (minQ.size() != 0 && arr[i] <= arr[minQ.peek()]) {
                minQ.pollLast();
            }
            minQ.add(i);
        }
        boolean[] ans = new boolean[N];
        for (int i = 0, j = N, offset = arr[i]; j < M; j++, offset = arr[i++]) {
            if (arr[minQ.peekFirst()] - offset >= 0) {
                ans[i] = true;
            }
            if (minQ.peekFirst() == i) {
                minQ.pollFirst();
            }
            while (!minQ.isEmpty() && arr[minQ.peekLast()] >= arr[j]) {
                minQ.pollLast();
            }
            minQ.add(j);
        }
        return ans;
    }
}
